package com.example.algorithm.a;

import java.util.Arrays;

/**
 * @author: dangwen
 * @createDate: 2021/3/31
 * 凑零钱问题:
 * 给你 k 种⾯值的硬币，⾯值分别为 c1,c2,c3...ck ，每种硬币的数量⽆限，再给⼀个总⾦额 amount
 * 	，问你最少需要⼏枚硬币凑出这个⾦额，如果不可能凑出，算法返回-1
 */
public class CoinChange {

    public static int coinChange(int[] coins, int amount) {
        //(1)初始化备忘录。下标对应金额，不包括0
        memo = new int[amount + 1];
        //(2)DFS返回零钱搭配为最少数量硬币
        return dfs(coins, amount);
    }

    //备忘录
    static int[] memo;
    public static int dfs(int[] coins, int amount) {
        //(1)base case，当amount<0，说明amount不足以减去某面额硬币
        if (amount < 0) return -1;
        //零钱0返回0个硬币
        if (amount == 0) return 0;
        //(2)查找备忘录，存在直接返回
        if (memo[amount] != 0) return memo[amount];
        //需要保存最小硬币方案，res的范围可取(最大数量硬币可能,MAX_VALUE)。此题最小硬币为1元，所以res可取(amount+1,Integer.MAX_VALUE)
        int res = Integer.MAX_VALUE;
        //(3)遍历每一种面额的硬币
        for (int coin : coins) {
            //(3.1)DFS传递减去该枚硬币的金额amount - coin，并返回兑换的硬币数
            int count = dfs(coins, amount - coin);
            //(3.2)当amount-coin即不足以减去某面额硬币时触发basecase返回-1，直接跳过该种硬币可能性
            if (count == -1) continue;
            //(3.3)一个零钱数字存在多种硬币搭配方案，保存需要最少硬币的搭配方案
            res = Math.min(res, 1 + count);
        }
        //(4)保存至备忘录
        memo[amount] = res != Integer.MAX_VALUE ? res : -1;

        return memo[amount];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{2,5,10,20};
        int amount = 9;
        int i = coinChange1(coins, amount);
        System.out.println(i);
    }

    public static int coinChange1(int[] coins, int amount) {
        if (amount == 0) return 0;
        //(1)初始化DP table，零钱为0则硬币0个
        int[] dp = new int[amount + 1];
        dp[0] = 0;

        //(2)遍历每种【状态】即金额，【选择】即保存最少硬币数量
        for (int amounttt = 1; amounttt <= amount; amounttt++) {
            //(1.1)初始化DP table。初始为最大硬币数量即amount个，因为最小面额为1元，那么+1即为无法到达的硬币个数。当然取(amount+1,Integer.MAX_VALUE - 1)(ps:后面存在1+dp[balance]计算)范围都可
            dp[amounttt] = amount + 1;
            //(3)遍历每种面额的硬币
            for (int coin : coins) {
                //(3.1)剩余金额balance，为当前amount-某额度硬币
                int balance = amounttt - coin;
                //(3.2)剩余额度>=0，说明该种硬币的组合可行
                if (balance >= 0) {
                    //(3.3)说明amount额度足以减去某额度硬币。balance<amounttt，balance于前面已经计算保存好【状态】，+1为加上当前硬币
                    //例如1：coins[1,2,5]，amounttt=4
                    //①balance=4-1，此时dp[4]=min(初始值,1+dp[3]）,而dp[3]由1元+2元组合为2枚。保存最小值dp[4]=3
                    //②balance=4-2，此时dp[4]=min(初始值,1+dp[2])，而dp[2]由2元组合为1枚。保存最小值dp[4]=2
                    //③balance=4-5，不足以减去该面额
                    //例如2:coins[3]，amounttt=5。dp则为[0,max,max,1,max,max,max]，毕竟max<max+1
                    dp[amounttt] = Math.min(dp[amounttt], 1 + dp[balance]);
                }
            }
        }

        //(4)如amount等于初始值，说明在给定种类的硬币中无法组合成amount元。比如coin[2,3] amount=1,4...
        return dp[amount] == (amount + 1) ? -1 : dp[amount];
    }

    public int coinChange3(int[] coins, int amount) {
        if(amount == 0) return 0;
        if(amount <= 0) return -1;
        return coindp(coins,amount);
    }

    //状态：金额
    //转移：一个硬币，这个硬币的金额在coins[]数组中遍历
    //dp函数：输入金额，返回最少硬币数
    public int coindp(int[] coins, int amount){
        int[] dp = new int[amount+1];//最多的硬币情况是全部是1元，共有amount个硬币，共有amount+1个状态，amount+1个金额
        Arrays.fill(dp, amount+1);//必须将所有的dp赋最大值，因为要找最小值
        dp[0] = 0;//自底向上，金额为0，最小硬币数为0
        int[] mem = dp;
        for(int am = 1; am <= amount; am++){//自底向上
            for(int coin : coins){//遍历coins的金额
                if(am >= coin)//am-coin 必须大于0，否则数组溢出
                    dp[am] = Math.min(dp[am], dp[am-coin] + 1);//金额为11的最小硬币数 和 金额为(11-一个面值)的最小硬币数+1 比较最小值
            }
        }
        return dp[amount]>amount? -1: dp[amount];//返回金额为amount的最小硬币数 根据测试用例判断dp[amout]>amount
    }
}
